This invention relates to a technique for multiplication in Galois Field arithmetic and more specifically to a multiplier for a Galois Field 256 arithmetic. Galois Field 256 arithmetic multipliers have a specific application in decoders for Reed-Solomon codes.
Reed-Solomon codes are used as error correcting codes in a wide variety of commercial applications such as compact discs, high speed cable modems, modulation systems for set-top box applications and the current HDTV standard. These codes are typically applied to data transmissions in which the data is transmitted by bytes, thus the interest is in Galois Field 256 arithmetic, as this accommodates 8-bit variables. In Galois Field 256 arithmetic, bytes are also called symbols. The Digital Audio-Visual Council (DAVIC) standard specifies a 204/188/8 Reed-Solomon code. The 204, also known as N, is the number of symbols in the channel codeword. The 204 symbols broadcast over the channel is called a frame. The 188, also known as K, is the number of symbols of information in the source codeword. The 8, also known as T, is the number of errors that can be corrected; the number of errors being equal to one-half of the difference of N and K. In this case, 188 bytes of data has 16 bytes of error correcting codes added to generate 204 bytes per frame. This code can correct for 8 errors in the frame. The correction involves the determination of both the location and the magnitude of the error. A problem with Reed-Solomon codes is that it forces the burden of computation upon the decoder, rather than on the encoder. For example, the code required in the DAVIC standard requires 16 Galois Field multiplications in the encoder and 2,550 Galois Field multiplications in the decoder. In view of the fact that the multiplications performed at the encoder are normally at the broadcast or recording studio level, the cost of such equipment can be amortized over the number of listeners/viewers. However, the decoder must be owned by each listener/viewer where its cost becomes a significant issue.
FIG. 1 shows a typical application of a decoder for Reed-Solomon codes employing Galois Field 256 arithmetic shown generally as 100 in FIG. 1. The signal to be decoded is applied to a delay 102 and a decoder circuit 106 via line 104. The purpose of delay 102 is to delay the signal the amount of time it takes for the decoder 106 to perform the decoding operations. The delay 102 may be a RAM of suitable length, for example. The output of the delay 102 is applied to a circuit 112 as is the output of decoder circuit 106 via line 110. Circuit 112 contains a RAM and the Galois Field arithmetic circuitry to make the corrections to the stored data where errors have been detected. This could involve Galois Field addition of an error correction to the data containing the error, for example. If it would be desirable that the delay be 100 clock cycles, for example, then the RAM 102 would store 100 bytes, after which the data would be loaded into the RAM of circuit 112. The RAM of circuit 112 would have a capacity of 204 bytes, for example, under the DAVIC standard. As the RAM reaches capacity, errors on line 110 would be output to the RAM of circuit 112, in order to correct the errors. By the time the 204 clock cycles of the frame have been completed, all of the entries into the RAM have been made and all the corrections to those entries have also been made. Then data is taken from the top or zero address of the RAM and output to a display (not shown) on line 114 and a new entry is applied to that slot via line 108 and the process repeats. Longer delay times increases the latency of the signal and the size of the RAM that is required for the delay 102.
FIG. 2 shows a prior art polynomial multiplier for Galois Field 256 arithmetic which takes 8 clock cycles to complete the computation. The notation xe2x80x9c(7:0)xe2x80x9d refers to bits 7-0 of the variable A. The circuit comprises of two multiplexers having inputs of A (6:0) and B (7:0) respectively. The output of multiplexers on lines 214 and 216 are input into registers 220 and 222 respectively. The output of registers 220 and 222 on lines 226 and 230 are fed back to multiplexers 210 and 212 via lines 206 and 208 respectively. Lines 226 and 230 are also fed into multiplexers 238 and 240, respectively. The second input to multiplexer 238 is A (7) on line 228 and the second input to multiplexer 240 is B (7:0) on line 232. The output of the multiplexers 238 and 240 on lines 244 and 246 is input into A-block 248 to produce the result C (7:0) on line 250. Line 250 is coupled into X-block 254 via line 250. The output of X-block 254 on line 218 is the result of Y(7:0) which is fed back to register 224 the output of which is fed via line 234 to multiplexer 242, which also has an input of (0) on line 236. The output of multiplexer 242 on line 252 is Y1(7:0) which is also input into X-block 254. The first cycle ANDs the most significant bit of A with B(7:0), XORs the result with Y(6:0), XORs the primitive polynomial and stores the result. The A register stores the one-bit left-shifted result. The least significant bit is loaded with a 0. These operations are repeated seven more times which produces the file output. This circuit is well known in the prior art.
Returning to FIG. 1, if the delay 102 is desirably no more than 100 clock cycles, for example, and the DAVIC standard is applied, the number of polynomial multipliers for the Galois Field 256 arithmetic that is required is:
2,550 divided by 100=25.5=26
However, the fact that the prior art multipliers require 8 clock cycles to perform a single multiplication, means that 8 times that number of multipliers is required, 8 times 25.5 equalling 204 multipliers in a single decoder. It must be remembered that each CD player, set-top box, etc., that contains a Reed-Solomon decoder must have this number of Galois Field multipliers. The number of multipliers can be decreased by increasing the delay of the delay element 102, but this increases the size of the RAM that is required and increases the latency of the signal. This problem is exasperated by the fact that realizing Reed-Solomon codes for correcting video signals will require a data rate of 5 megabytes per second. If the techniques of the prior art are utilized, this would require a clock frequency of 40 MHz for a single clock cycle multiplier.
Polynomial multipliers for Galois Field arithmetic are very different from multipliers for infinite field variables and are non-intuitive. This can be seen from a simple multiplication example involving Galois Field 4 arithmetic, shown in Table 1. Galois Field 4 arithmetic is illustrated because the table has only 16 entries whereas a table for Galois Field 256 arithmetic has 65,536 entries.
Galois Field 4 arithmetic involves the numerals 0,1,2 and 3 only. It takes only a quick glance at Table 1 to realize how different Galois Field arithmetic multiplications are. According to the table, multiplication of 3xc3x973 yields a result of 2 which is quite astonishing to those not familiar with Galois Field arithmetic.
Galois Field 256 arithmetic contains a set of 256 numbers from 0 to 255. This produces the 65,536 possible combinations referred to above. The large number of possible combinations make other solutions such as the required number of look-up tables (LUTs) impractical. Accordingly, there is a need for a low cost, high speed Galois Field 256 multiplier which is particularly applicable to a decoder for Reed-Solomon codes.
It is a general object of the present invention to provide a method and apparatus for Galois Field multiplication.
It is a further object of the present invention to provide a method and apparatus for Galois Field 256 arithmetic multiplication.
A still further object of the present invention is to provide a method and apparatus for Galois Field 256 multiplication for a Reed-Solomon code decoder.
Yet another object of the present invention is to provide a low cost method and apparatus for Galois Field 256 multiplication for a Reed-Solomon code decoder.
These and other objects, advantages and features are provided, in accordance with one aspect of the present invention by a combinatorial polynomial multiplier for Galois Field arithmetic. An AND block includes a plurality of 2-input AND gates, the plurality having a number of gates equal to the product of the number of bits in a multiplicand multiplied by the number of bits in a multiplier, each gate having as inputs one bit of the multiplicand and one bit of the multiplier and generating a minterm as an output. An exclusive OR block includes a plurality of 2-input exclusive OR gates in a binary exclusive OR tree, inputs of the exclusive OR block being coupled to the outputs of the AND block to receive the minterms derived from a primitive polynomial for said Galois Field arithmetic for generating a Galois Field product as an output.
Another aspect of the invention comprises a polynomial multiplier for a decoder for Reed-Solomon codes utilizing Galois Field arithmetic. The multiplier includes a combinatorial logic circuit consisting of AND gates and exclusive OR gates.
A further aspect of the invention includes a method of multiplying a Galois Field arithmetic multiplicand by a Galois Field arithmetic multiplier to generate a Galois Field arithmetic product. Each bit of the multiplicand is ANDed with each bit in the multiplier to generate a plurality of minterms equal in number to the product of the number of bits in the multiplicand multiplied, by the number of bits in the multiplier. The minterms are exclusive ORed in an exclusive OR tree for each bit in the product, each tree exclusive ORing the minterms derived from a primitive polynomial for the Galois Field arithmetic for generating a bit of said Galois Field product.
A still further aspect of the invention comprises a method of multiplying polynomials in a method of decoding Reed-Solomon codes utilizing Galois Field arithmetic. An n-bit multiplicand and an n-bit multiplier are provided. The multiplicand is multiplied by the multiplier in an n-bit combinatorial logic circuit Galois Field arithmetic multiplier.